Bound on Global Extremum

Adapted from: SOSTOOLS' SOSDEMO3 (See Section 4.3 of SOSTOOLS User's Manual)

using DynamicPolynomials
@polyvar x1 x2

(x1, x2)

The Goldstein-Price function $f(x)$ is defined as follows:

f1 = x1 + x2 + 1
f2 = 19 - 14x1 + 3x1^2 - 14x2 + 6x1*x2 + 3x2^2
f3 = 2x1 - 3x2
f4 = 18 - 32x1 + 12x1^2 + 48x2 - 36x1*x2 + 27x2^2
f = (1 + f1^2 * f2) * (30 + f3^2 * f4)

\[ 144x1^{8} - 288x1^{7}x2 - 648x1^{6}x2^{2} + 1224x1^{5}x2^{3} + 1305x1^{4}x2^{4} - 1836x1^{3}x2^{5} - 1458x1^{2}x2^{6} + 972x1x2^{7} + 729x2^{8} - 768x1^{7} + 1344x1^{6}x2 + 2592x1^{5}x2^{2} - 4080x1^{4}x2^{3} - 3480x1^{3}x2^{4} + 3672x1^{2}x2^{5} + 1944x1x2^{6} - 648x2^{7} + 952x1^{6} - 168x1^{5}x2 - 5370x1^{4}x2^{2} + 1240x1^{3}x2^{3} + 8730x1^{2}x2^{4} - 1188x1x2^{5} - 4428x2^{6} + 1344x1^{5} - 7680x1^{4}x2 + 9840x1^{3}x2^{2} + 5040x1^{2}x2^{3} - 11880x1x2^{4} + 1944x2^{5} - 2454x1^{4} + 5784x1^{3}x2 + 7776x1^{2}x2^{2} - 23616x1x2^{3} + 14346x2^{4} - 1072x1^{3} + 7344x1^{2}x2 - 19296x1x2^{2} + 12288x2^{3} + 1260x1^{2} - 4680x1x2 + 3060x2^{2} + 720x1 + 720x2 + 600 \]

We need to pick an SDP solver, see here for a list of the available choices. We use SOSModel instead of Model to be able to use the >= syntax for Sum-of-Squares constraints.

using SumOfSquares
using CSDP
solver = optimizer_with_attributes(CSDP.Optimizer, MOI.Silent() => true)
model = SOSModel(solver);

We create the decision variable $\gamma$ that will be the lower bound to the Goldstein-Price function. We maximize it to have the highest possible lower bound.

@variable(model, γ)
@objective(model, Max, γ)

\[ γ \]

We constrain $\gamma$ to be a lower bound with the following constraint that ensures that $f(x_1, x_2) \ge \gamma$ for all $x_1, x_2$.

@constraint(model, f >= γ)

JuMP.optimize!(model)

We verify that the solver has found a feasible solution:

JuMP.primal_status(model)

NEARLY_FEASIBLE_POINT::ResultStatusCode = 2

We can now obtain the lower bound either with value(γ) or objective_value(model):

objective_value(model)

2 . 9 9 9 9 7 3 5 5 0 3 3 6 6 4 6 3

This page was generated using Literate.jl.